Arnoldi 算法

阐述

设矩阵为 $m$ 维，给定 $n$ ，通过 Krylov 子空间法和 Gram-Schmidt 正交化来找到一组条件数好的 $n$ 维正交基，并排列成一个矩阵。这个矩阵满足：

AQ_n=Q_{n+1}\hat H_n

其中 $\hat H_n$ 是一个接近于上三角矩阵的 $(n+1)\times n$ 矩阵。这个也可以写成

AQ_n=Q_nH_n+q_{n+1}e_n^*h_{n+1,n}

因此，有 $Q_n^*AQ_n=H_n$ 。接下来，要找到 $x\in\mathcal K_n$ 来使得 $Ax=\nu x+r$ 中残差最小。

要求残差垂直于子空间，代入 $x=Q_nz$ 即得到

H_nz=\nu z

这是一个比较小的特征值问题，可以用 QR 分解等方法求解；得到的 $\{x_k,\nu_k\}$ 称为 Ritz 向量和 Ritz 值。

注意到 $H_n$ 是三对角矩阵，所以在计算正交化的时候绝大多数点积都不需要计算，将总的复杂度从 $O(mn^2)$ 降到了 $O(mn)$ 。

解决方式是在 $n=k+\rho$ 步之后重启，只留下 $k$ 个「最好的」向量，然后从第 $k$ 步开始继续跑。例如，如果只需要最大的一个特征值，那么让 $k=1$ 即可。

比较适合于「极限」的 $\lambda$ 数值。因此，如果希望找到一个接近于 $\mu$ 的特征值，可以对 $(A-\mu I)^{-1}$ 用 Arnoldi 法。